import typing


# 题目：地上有一个m行n列的方格， 一个机器人从坐标（0，0）的各自开始移动，，他每次可以向左、右、上、下移动一格，但不能进入行坐标与列坐标位数之和大于k的格子

# 通过回溯法解决，遍历每个位置

def moving_count(threshold, rows, cols):
    if threshold < 0 or rows <= 0 or cols <= 0:
        return 0

    visited = [[0 for j in range(cols)] for i in range(rows)]
    # print(visited)
    count = moving_count_core(threshold, rows, cols, 0, 0, visited)

    return count


def moving_count_core(threshold, rows, cols, row, col, visited):
    count = 0
    if check(threshold, rows, cols, row, col, visited):
        visited[row][col] = 1
        count = 1 + moving_count_core(threshold, rows, cols, row + 1, col, visited) + \
                moving_count_core(threshold, rows, cols, row - 1, col, visited) + \
                moving_count_core(threshold, rows, cols, row, col + 1, visited) + \
                moving_count_core(threshold, rows, cols, row, col - 1, visited)
    return count


# 检查一个格子能不能进入
def check(threshold, rows, cols, row, col, visited):
    if 0 <= row < rows and 0 <= col < cols and \
            get_digit_sum(row) + get_digit_sum(col) <= threshold and \
            not visited[row][col]:
        return True
    return False


# 计算数字的数位之和
def get_digit_sum(num):
    s = 0
    while num > 0:
        s += num % 10
        num = num//10
    return s

if __name__ == '__main__':
    print(moving_count(2, 5, 5))
    print(get_digit_sum(23))

